package question;

public class T0223_01bag_Demo {

    public static int checkBag(int[] volume, int[] weight, int totalVolume) {
        int n = volume.length;
        int[] dp = new int[totalVolume + 1];
        for (int i = 1; i <= totalVolume; i++) {
            dp[i] = dp[i-1];
            for (int j = 0; j < n; j++) {
                if (volume[j] <= i) {
                    dp[i] = Math.max(dp[i-volume[j]] + weight[j], dp[i]);
                }
            }
        }
        return dp[totalVolume];
    }

    public static int checkBag2(int[] volume, int[] weight, int totalVolume) {
        int n = volume.length;
        int[] dp = new int[totalVolume + 1];
        for (int i = 0; i < n; i++) {
            for (int j = volume[i]; j <= totalVolume; j++) {
                dp[j] = Math.max(dp[j], dp[j - volume[i]] + weight[i]);
            }
        }
        return dp[totalVolume];
    }

    public static int checkBag3(int[] volume, int[] weight, int totalVolume) {
        int n = volume.length;
        int[] dp = new int[totalVolume + 1];
        for (int i = 0; i < n; i++) {  // 外层循环遍历物品
            for (int j = totalVolume; j >= volume[i]; j--) { // 内层循环遍历背包容量，从大到小
                dp[j] = Math.max(dp[j], dp[j - volume[i]] + weight[i]);
            }
        }
        return dp[totalVolume];
    }


    public static int checkBag4(int[] volume, int[] weight, int totalVolume) {
        int n = volume.length;
        int[] dp = new int[totalVolume + 1];
        for (int j = totalVolume; j >= 0; j--) {  // 外层循环遍历背包容量，从大到小
            for (int i = 0; i < n; i++) { // 内层循环遍历物品
                if (volume[i] <= j) {
                    dp[j] = Math.max(dp[j], dp[j - volume[i]] + weight[i]);
                }
            }
        }
        return dp[totalVolume];
    }

    public static void main(String[] args) {
        int[] volume = new int[] {3, 20, 4, 1};
        int[] weight = new int[] {7, 39, 9, 2};
        System.out.println(checkBag(volume, weight, 1091));
        System.out.println(checkBag2(volume, weight, 1091));
        System.out.println(checkBag3(volume, weight, 1091));
        System.out.println(checkBag4(volume, weight, 1091));
    }
}
